Most modern radio communication systems transmit data over time-varying, dispersive communication channels. Among the distortions introduced by the channel, inter-symbol interference (ISI) is significant because it severely degrades the performance of the receiver. To mitigate the effects of ISI, many receivers use equalizers. The general architecture of an equalizer comprises filters, adders for combining the output of the filters, and decision devices. The filters are linear finite-impulse-response (FIR) with complex coefficients. A decision device operates on complex inputs and outputs complex values that are representative of the signal constellation points of the modulation scheme.
In general, the equalizer filter coefficients are jointly optimized according to a criterion suitable for the communication system. Determining the optimal equalizer filter coefficients is a computationally intensive task because it requires the solution to a large set of linear equations. Two general approaches are commonly used today: the first approach is the adaptive approach, and the second is the direct matrix inversion approach.
In the adaptive approach, the equalizer filter coefficients are first set to some initial values. The output error signal, defined as the difference between the input and the output of the equalizer decision device, is then used to recursively adjust the equalizer filter coefficients toward the optimal settings. Depending on the coefficient adaptation algorithm employed, a training sequence may be required. A training sequence is a known set of symbols that the transmitter sends along with the data. In U.S. Pat. No. 5,068,873 issued to Murakami, the least mean square (LMS) or Kalman filter algorithm is used for adaptation. A training sequence is required for that approach. The LMS algorithm requires O(N) complex operations per iteration, where N is the total number of coefficients to optimize. Furthermore, a large number of iterations (>>N) is required for the equalizer filter coefficients to converge to the optimal values. While Kalman filter algorithm converges faster to the optimal solution, it requires O(N2) operations per iteration. Similarly, U.S. Pat. No. 5,283,811 issued to Chennankeshu, et al. employs the fast Kalman algorithm for decision-feedback equalizer (DFE) coefficient adaptation. U.S. Pat. No. 3,974,449 issued to Falconer describes a DFE adaptation method that does not use training sequences.
In the direct matrix inversion approach, a response of the channel to the signaling pulse is first estimated. This estimate is the response, filtered by the receiver filter, of the channel to the transmitter spectral-shaping pulse. The equalizer coefficients are then obtained from the estimate of the response of the channel to the signaling pulse by solving a set of complex-valued linear equations. In general, the solution of these equations requires the inversion of an N×N square matrix, which requires O(N3) complex multiplications. U.S. Pat. No. 5,436,929 issued to Kawas Kaleh utilizes positive-definite and Hermitian symmetric properties of the square matrix so that a Cholesky decomposition can be used. The Cholesky decomposition requires O(N3) complex multiplications to factor a positive-definite, Hermitian symmetric matrix into the product of lower and upper triangular matrices. The upper triangular matrix is equal to the Hermitian transpose of the lower triangular matrix. The triangular matrices are easily invertible, requiring O(N3) multiplications. U.S. Pat. No. 5,790,598 issued to Moreland, et al. describes a recursive method using the Cholesky decomposition. Both of these techniques still require O(N3) complex multiplications.
In general, the optimization of the equalizer coefficients requires at least O(N3) complex multiplies if direct matrix inversion is used. This complexity makes the method impractical to implement in many real life communication system. The complexity may be even greater for the adaptive approach if a large number of iterations are required. Moreover, the adaptive approach usually results in sub optimal solution compared to the direct matrix inversion method.
It should be noted that in the present specification, the mathematical notations used are such that uppercase notation, e.g. W, is used to denote a matrix, and lowercase notation, e.g. w, is used to denote a vector.
FIG. 1, shows a generic equalizer device 10 used in a communication system. The equalizer 10 is designed to restore the transmitted signal distorted by dispersive channel (characterized by channel response matrix H) and noise (characterized by variance σ2). In order to compute filter coefficients for the equalizer, a channel response matrix G is computed based on estimate of channel response matrix H. This step is commonly performed using pilot signaling. The signal processing is usually done in the equalizer 10 in block by block fashion. A first channel matrices estimation block 12 receives input signals (vector r) for use in estimating channel response matrices H and G. The filter coefficients vectors are then computed in a filter coefficients calculation block 14 where the computation involves the inversion of channel response matrix G. The computed filter vector w0 is then used to equalize the received vector r by means of an FIR filter 16 to obtained the output data subsequently used in a communication receiver.
In order to understand the computational complexity of the inversion of channel response matrix G, a typical method for matrix inversion will now be described.
The vector of channel estimates h is used for computation of the vector f where, for example, for five multipaths and three timing positions per multipath,
                              h          =                    ⁢                      [                                          h                                  -                  0                                            ,                              h                0                            ,                              h                                  +                  0                                            ,              0              ,              …              ⁢                                                          ,              0              ,                              h                                  -                  1                                            ,                              h                1                            ,                              h                                  +                  1                                            ,                                                                              ⁢                      0            ,            …            ⁢                                                  ,            0            ,                          h                              -                5                                      ,                          h              5                        ,                          h                              +                5                                      ,            0            ,            …            ⁢                                                  ,            0                    ]                          f    =          [                        f          ⁡                      (            0            )                          ,                  f          ⁡                      (            1            )                          ,        …        ⁢                                  ,                  f          ⁡                      (                          N              -              1                        )                              ]                  f      ⁡              (        i        )              =                  ∑                  n          =          0                          n          =                      N            -            1            -            i                              ⁢                          ⁢                        h          ⁡                      [            n            ]                          ⁢                              h            ⁡                          [                              n                +                i                            ]                                *                    
Construct matrix G as follows:
      G    =          [                                                                  f                ⁡                                  (                  0                  )                                            +              β                                                          f              ⁡                              (                1                )                                                          ⋯                                              f              ⁡                              (                                  N                  -                  1                                )                                                                                        f              ⁡                              (                                  -                  1                                )                                                                                        f                ⁡                                  (                  0                  )                                            +              β                                                                                                                    f              ⁡                              (                                  N                  -                  2                                )                                                                          ⋮                                ⋮                                ⋰                                ⋮                                                              f              ⁡                              (                                                      -                    N                                    +                  1                                )                                                                        f              ⁡                              (                                                      -                    N                                    +                  2                                )                                                          ⋯                                                              f                ⁡                                  (                  0                  )                                            +              β                                          ]                  f      ⁡              (                  -          i                )              =                                        f            ⁡                          (              i              )                                            *                                                                ⁢                                  ⁢        and        ⁢                                                  ⁢                                                ⁢                  f          ⁡                      (            0            )                              >      0      
Since the channel response matrix G is Hermitian and positive definite, there is unique lower (upper) triangular matrix L(U) such that G=LLH=UHU , when the superscript H indicates the Hermitian transpose of a matrix. In general, we haveGG−1=IL(LHG−1)=ILD=I  (1)where the superscript −1 indicates the inverse of a matrix and I is the identity matrix. Moreover, we also haveLHG−1=D  (2)
To find the inverse channel response matrix G−1, the following steps need to be carried out:                Step 1: Perform a Cholesky decomposition of the channel response matrix to obtain the lower triangular matrix L—calculation complexity O(N3).        Step 2: Solve equation (1) to get matrix D using Forward Substitution as the lower triangular matrix L.        Step 3: Solve equation (2) to get the inverse channel response matrix G−1 using Backward Substitution on the matrices D and LH.        
Since the system of linear equations has N times N unknowns (D and G−1 are N×N matrices), Steps 2 and 3 in the above-described method has a calculation complexity of O(N3).
Using a method, such as that described in co-pending Australian patent application no. 2005203278, in the name of NEC Australia Pty Ltd, filed on 26 Jul. 2005 and entitled “Method for calculating filter coefficients for an equalizer in a communication receiver,” the calculation complexity of steps 2 and 3 can be reduced to O(N2). In this case the complexity of the decomposition step (Step 1) becomes the main contributor to the complexity, processing time and size in computing the equalizer filter coefficients in an equalizer.
Thus there is a need for an efficient method for computing the equalizer filter coefficients in an equalizer that can practically be implemented in a communication receiver. It would be desirable for the method for computing the equalizer filter coefficients to be computationally less complex than currently known methods. It would also be desirable to provide a method for computing the equalizer filter coefficients with fewer computations as this can lead to a reduction in the circuit area required and power consumed and/or faster processing times. It would also be desirable to provide a method for computing the equalizer filter coefficients in an equalizer that ameliorates or overcomes one or more problems of known coefficient computation methods.